package com.example.leetcode.DFS;

/**
 *
 * 题目描述
 * 给定一个字母矩阵，所有的字母都与上下左右四个方向上的字母相连。给定一个字符串，求
 * 字符串能不能在字母矩阵中寻找到。
 * 输入输出样例
 * 输入是一个二维字符数组和一个字符串，输出是一个布尔值，表示字符串是否可以被寻找
 * 到。
 * Input: word = "ABCCED", board =
 * [[’A’,’B’,’C’,’E’],
 * [’S’,’F’,’C’,’S’],
 * [’A’,’D’,’E’,’E’]]
 * Output: true
 * 从左上角的’A’ 开始，我们可以先向右、再向下、最后向左，找到连续的"ABCCED"。
 *
 * @Description https://leetcode-cn.com/problems/word-search/solution/hui-su-suan-fa-qiu-jie-by-sdwwld-2/
 * @date 2021/5/20 11:11
 * @Author liuzhihui
 * @Version 1.0
 */
public class Solution_6_79 {
    public static void main(String[] args) {
        char[][] board = new char[][]{{'A','B','C','E'},{'S','F','C','S'},{'A','D','E','E'}};
        String word = "ABCCED";

        boolean exist = exist(board, word);
        System.out.println(exist);

    }
    public static boolean exist(char[][] board, String word) {
        boolean result = false;
        char[] chars = word.toCharArray();

        // 遍历二维数组
        for (int i = 0; i < board.length; i++) {
            for (int j = 0; j < board[0].length; j++) {
                // 寻找
                if (dfs(board, chars, i, j, 0)){
                    return true;
                }
            }
        }
        return result;
    }

    private static boolean dfs(char[][] board, char[] chars, int i, int j, int pos ) {
        // 判断在i,j在不在二维数组上；判断当前元素是否等于当前的字符里对应的一个字符
        if (i < 0 || j < 0 || i >= board.length || j >= board[0].length || board[i][j] != chars[pos] ){
            return false;
        }
        // 在二维数组里找到了对应的字符串
        if (chars.length - 1 == pos){
            return true;
        }

        char c = board[i][j];
        // 表示被访问过,避免递归的时候，访问已经访问过的点
        board[i][j] = '.';
        // 指针移动
        pos++;

        // 上下左右各个方向去找
        boolean res = dfs(board, chars, i + 1, j, pos) || dfs(board, chars, i - 1, j, pos) || dfs(board, chars, i, j + 1, pos) || dfs(board, chars, i, j - 1, pos);

        // 回溯: 递归之后再把当前的坐标复原
        board[i][j] = c;

        return res;
    }

    // 练习
    public static boolean exist1(char[][] board, String word){

        char[] chars = word.toCharArray();

        // 遍历二维数组的元素
        for (int i = 0; i < board.length; i++) {
            for (int j = 0; j < board[0].length; j++) {
                if (dfs1(i, j, board, chars, 0)){
                    return true;
                }
            }
        }
        return false;
    }

    // 判断当前元素在不在二维数组上，当前元素和word的是否相等
    // 判断是否在二维数组中，找到字符串chars
    // 将当前元素替换为‘。’，移动index指针，以便对比下一个元素
    private static boolean dfs1(int i, int j, char[][] board, char[] chars, int index) {
        if(i < 0 || j < 0 || i > board.length || j > board[0].length || board[i][j] != chars[index]){
            return false;
        }
        if (index == chars.length -1){
            return true;
        }
        char c = board[i][j];
        board[i][j] = '.';
        index++;

        // 分别从上，下，左，右，四个方向找
        boolean b = dfs1(i - 1, j, board, chars, index) || dfs1(i + 1, j, board, chars, index)
                || dfs1(i, j - 1, board, chars, index) || dfs1(i, j + 1, board, chars, index);
        // 回溯：以防某个方向找不到匹配的字符串，需要回溯，然后再去其他方向找
        board[i][j] = c;

        return b;
    }
}
